1. Technical Field
The present invention relates to the field of memory management in a data processing system such as a computer. More specifically, the present invention relates to a system and method for controlling allocation of memory in a cache memory to maximize storage use and minimizes retries.
2. Description of the Related Art
The rapid development of microprocessors has created many challenges. As components are more densely packed on a microprocessor, the processor's speed of operation increases. In addition, techniques such as pipelining and multiple processor systems have created processing systems with very large data throughput needs. To meet this challenge, system designers have turned to cache memory systems.
Cache memory systems rely on the principle of locality of The locality of references principle states that a computer program will spend approximately ninety percent of its time accessing ten percent of its code. In addition, the next memory address accessed is usually an address near the last address accessed. Using these principles, a small portion of the memory may be fetched into a small, extremely fast memory called a cache. Using the principle of locality of references, data with a high probability of being accessed by the processor is stored in the cache. Thus, the processor retrieves the data directly from the very fast cache memory. This means that the processor will spend as little time as possible waiting for the necessary data from memory.
The development of cache systems has reached a very high level of sophistication. It is common in microprocessor-based systems to have two or more levels of cache. Often, the first level (L1) of cache is formed on same semiconductor substrate as the microprocessor. This provides maximum throughput between the first level cache and the processor. The second level (L2) cache is often a larger memory, which may be external or internal. The L2 cache provides a larger, but slower, data storage capability.
One of the more complex systems for using cache involves the use of pipelined associative caches. These systems can provide a very high data throughput. However, the allocation of cache space must be carefully managed.
A particular problem occurs when a miss occurs on two pipelined accesses. A cache miss occurs when a processor requests memory that is not stored in the cache and must be fetched from slower memory devices. A common technique is to allocate a way or write set for the missing data upon the first detection of a cache miss. The memory system then fetches the missed data block from system memory or a lower level cache and stores it in the allocated write set.
The problem arises when, during the pendency of the block allocation, a second pipelined access requests data from the same cache line as the pending allocation in a multiple way associative cache. In this circumstance, the cache memory controller may allocate another way or write set in the cache directory. This wastes space and can cause a system failure unless the cache controller is specifically designed to handle multiple, identical, valid tags at the same index. Therefore, there is a need for a system that avoids the misallocation of cache resources.